import java.util.Arrays;

public class Q3 {
    public static void main(String[] args) {
        int[][] grid = new int[][]{{10, 1,2,3,2},{1, 2,4,3,5}};
        int ans = maxPathScore(grid, 10);
        System.out.println(ans);
        // 不是一个简单的dp问题！！
    }

    public static int  maxPathScore(int[][] grid, int k) {
        int[][] dp = new int[grid.length+1][grid[0].length+1];
        dp[0][0] = 0;

        for (int i = 1; i <= grid.length; i++) {
            System.arraycopy(grid[i - 1], 0, dp[i], 1, grid[0].length);
        }
        dp[0][1] = 0;
        dp[1][0] = 0;
        if (grid[0].length - 1 >= 0) System.arraycopy(dp[1], 1, dp[0], 2, grid[0].length - 1);
        for(int i=2;i<=grid.length;i++) {
            dp[i][0] =  dp[i-1][1];
        }
        for(int i=1;i<dp.length;i++) {
            for(int j=1;j<dp[0].length;j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + dp[i][j];
            }
        }
        System.out.println(Arrays.deepToString(dp));
        return 1;
    }
}
